'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-25 21:31:44
'''
'''
410. 分割数组的最大值
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:

输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

tips:据说这种...中是最大值最小常可用二分法。
这个的关键就在于可以设置一个值x，用x去检验数组,考察以x为和的最小值可以将数组分成几份，
如果数组nums[i:j+1]的和大于x，则从nums[j+1]从新开始计算和，并将cnt+=1。

然后x的取值范围是max(nums)与sum(nums)之间，即可用二分法。
'''
from typing import List
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def cut_count(x):
            re = 1
            tmp = 0
            for i, v in enumerate(nums):
                tmp += v
                if tmp > x:
                    re += 1
                    tmp = v
            return re
        left = max(nums)
        right = sum(nums)
        while left<right:
            med = (left+right)//2  #技巧，这里与下面注释相配合，使程序不至于死循环。如果right = med为迭代
                                   #则这里要这样写。如果left=med迭代，则这里需要med = (left+right+1)//2
            count = cut_count(med)
            if count > m:
                left = med+1
            else:
                right = med
        return left
if __name__ == "__main__":
    solution = Solution()
    nums = [7,2,5,10,8]
    m = 2
    print(solution.splitArray(nums, m))